The present invention relates to the storage and retrieval of information by electromagnetically responsive recording means and, more particularly, to such storage and retrieval where the information is of a kind having relationships between portions thereof which affect the arrangement of the storage means.
Storage and retrieval of information in system components relying on electromagnetic means is a central consideration in computer systems. The capabilities of such system components for these purposes have grown by orders of magnitude in recent years, both short term storage capabilities for information which is to be kept nearly immediately available to the central processing unit in the system, and longer term storage capabilities for information desired to be kept for longer terms. Information stored for longer terms is typically not available nearly as quickly to the central processing unit of the system as that kept in short term storage, but is often very voluminous necessitating a different approach than for short term storage approaches as the cost of storage becomes an overriding factor for such large information quantities. Nevertheless, the rate at which the central processing unit has access to such large volumes of information in longer term storage is always desired to be as great as possible even though compromises with cost are necessary.
A form of information which is often placed in longer term storage is "relational"60 data. Such data has portions thereof, i.e. information items, related in some manner to one another. Such data can very commonly be represented in tabular form, a presentation which also shows the relationship between the information items. In such a tabular arrangement, the rectangular array of information items comprising the tabulation may have a column assigned to each type of information item and a row assigned to each record which comprises an associated set of such information types. For example, a set of information types, one per column, could be a person's name in the first column, then address in the second, then telephone number in the third, and so on for several other types of personal data. Thus, each row would have the name of a particular person followed by that person's associated specific information items (address, telephone number, etc.) under each information type column for that person.
A database management system, as part of a computer system, will be used to store and retrieve such data from the system longer term memory. Such a longer term memory in a sufficiently large system will be provided in a database device, or machine, of some type, today commonly a database processor directing the information storage and retrieval operations of the machine typically formed at one or more magnetic disk drives. In earlier times, such a database machine might have been a punched card reader or a magnetic tape drive.
In a punched card storage arrangement, each of the foregoing rectangular array, or tabular, records in a row would be typically contained in separate paper cards in the form of coded punch-outs so that, in effect, the rows are stored end-to-end. Similarly, each such row would also be provided end-to-end along a magnetic tape in a sequence of coded magnetization of a magnetic material permitting small portions thereof to be placed in one of two magnetization states, such tapes being used in a magnetic tape storage arrangement including a tape drive. Thus, in these systems, the storage space appears to the database management system as a long, linear space.
For the most part, this same linear storage space concept has been provided in rotating magnetic disk storage arrangements currently used in database machines through having such rectangular array row records provided end-to-end along each concentric recording track present in the alterable state material on the face of the disk. Thus, with respect to a movable arm carrying a storage and retrieval sensing ("head") means over a disk recording track rotating therebelow, the information again appears to be stored in a long, linear space since the information is only available when the proper portion of the recording track has rotated past below this head. If the information is in another one of the recording tracks, the movable arm with the head must first be moved to that track with that track then permitted to rotate past therebelow until the desired portion of the track comes beneath the storing and sensing means. As a result of the sequential recording track motion past the head of the rows stored end-to-end as is the common practice, there will often be substantial delays in either storing or retrieving information in response to a request to do so by the central processing unit of the computer system.
Such magnetic disk storage arrangements have a magnetic disk formed by magnetic material deposited on a substrate, which material can have small portions therefor in one of two magnetization states along a series of concentric circular recording tracks. Each recording track is thus formed by a succession of magnetization regions, or storage sites, in each of which the magnetization state can be altered by an external magnetic field, and which are magnetized in accordance with the information item stored therein. Thus, during a storing operation, the succession of magnetization states in successive storage sites along a recording track are altered in accordance with each information symbol received by the database machine. These information symbols will be provided from other parts of the computer system in some coding scheme to differentiate successive information item representations from one another. These successive storage sites forming a recording track are then moved underneath the head to have magnetization states altered if new information is being stored ("written"), or to cause an electrical signal if the magnetization states present already represent an earlier storage of information which is now to be retrieved or "read out."
Alternative storage arrangements exist for database machines. In one of these, magnetic bubble storage memory, the alterable magnetization storage sites are magnetically moved to the stationary storing and retrieving means. A magnetic material substrate in which the magnetic domains ("bubbles" ) can be moved magnetically has various sector loops arranged to permit the bubbles therein to be continually moved past a transfer station to a track loop under the control of rotating magnetic fields. Each sector loop can be considered an analog of a recording track in a magnetic disk in which the presence or absence of bubbles represents information as does one or the other magnetization in a disk. Information can be taken from or provided to a sector loop from the track loop at the transfer station, the track loop in turn moving a bubble domain with this information between the sector loops and a storing and retrieving means, formed by a sense amplifier and its transfer station.
Several approaches to reducing delays in storing and retrieving, i.e. reducing the time to reach the storage sites for such activities or "access" time in magnetic disk machines, have been previously resorted to. One of these is to have the start of the adjacent concentric recording track on the face of the rotating disk begin at some angular distance from the end of the preceding track. This gives the movable arm, with the head thereon, time to move from over the end of the first track to being over the adjacent track before information need be stored or retrieved from this adjacent track. Thus, the starts of next adjacent recording tracks are skewed angularly oppositely to the direction of rotation from the ends of preceding adjacent tracks.
Another approach has been to interleave sequentially ordered, defined length storage site sectors along recording tracks which are to have information items stored in or retrieved from by the head successively in sequential order to thereby give sufficient time for one such operation on each sequential storage site sector before beginning an operation on the next. Thus, a first storage site sector along a circular recording track on a rotating magnetic disk will have a first row record provided therein followed by a second storage site sector which is either blank or storing some other unrelated information or another row record not next in sequence. The following third storage site sector along the recording track will have the following second row record therein, etc.
Hence, a retrieval can be completed with respect to the first row record in the first storage site sector during the time the storage and recording head is over both the first and second storage site sectors so that the system will be ready to retrieve the second row record placed in the third storage site sector when that third sector comes underneath the head. This interleaving arrangement may be continued along the circular recording track and then along the next track. However, this interleaving arrangement presupposes that row records from a tabular arrangement will be read successively, a supposition which does not necessarily hold true in many data storing and retrieving situations where, for example, successive columnar retrievals may at times be desired.
Thus, another possibility which arises is that the columnar information items may be desired to be retrieved successively rather than the row records. This desire, of course, could be best accommodated by end-to-end storing of the columns of information items along the recording tracks rather than end-to-end storing of row information items. Nevertheless, this still views the disk recording tracks as essential a long, linear recording space leaving a slow retrieval situation on these occasions that retrieval by rows is necessary.
Beyond these approaches, there have been several approaches which rely on parallel operation to a greater or lesser extent to shorten the time of access to desired storage locations on the face of a magnetic disk for storing or retrieving information thereat. One possibility is to provide a movable arm with a storing and retrieving head thereon for each concentric recording track on the face of the magnetic disk. Unfortunately, somewhere around 70% of the cost of a single movable arm disk drive is associated with that arm and head and its associated electronic circuitry. Increasing the number of such arms and heads, and adding the associated circuitry, would be prohibitively costly for a magnetic disk permitting a track density such that 300 tracks could be provided thereon, a not uncommon track density. Similarly, there can be provided a plurality of sense amplifiers in the magnetic bubble memory structure just as there can be provided a plurality of movable arms with heads in a magnetic disk drive. Again, however, the additions of added sense amplifiers, and associated structures in the bubble memory structure, lead to the need for greater surface area in the chip which rapidly increases the cost, as does the addition of additional associated electronic circuitry. In the same manner, there could be provided multiple storing and retrieving means in the form of additional lasers and light sensors for each optical disk recording track, but again with substantial additional costs.
Another alternative for a database machine is use of an optical disk in which again there are circular concentric recording tracks along which the information is comprised by the presence or absence of pits in the surface material of the disk. Such presence or absence of pits leads to reflections or lack of reflected light provided by a laser which are sensed by a light detector.
As indicated, storing of information in such a disk is accomplished by providing such pits along the recording track in accord with the information being stored. Currently, this arrangement leads to recording information on such an optical disk just once through the pits altering the state of the material on the recording track. Thereafter, information can only be read from such a disk without the opportunity to again record different information in the same storage locations. There are developments of alternative kinds of optical disks which would permit such restoring of information.
Rather than adding additional storage and retrieving means in parallel to more quickly be able to store or retrieve information from an individual storage means such as a magnetic disk, there can be provided parallel disk drive systems or parallel database machines of a standard kind without necessarily adding increased numbers of storing and retrieving means in parallel in each. Instead, the plurality of such longer term storage arrangements can be operated in concert to provide storing and retrieving of information in parallel for the central processing unit of the computer system. However, such parallel data streams lead to extensive control requirements which can rapidly increase the cost of the system and can lead to a slowing of system operation.
As can be seen, reducing the expense of storing voluminous data for longer terms has yielded only to the use of data storage arrangements that permit access to selected ones of a plurality of storage sites therein only in a sequence which follows the sequential ordering of the storage sites along what is, or is analogous to, a single line path in that alterable state material in which the storage sites are provided. The desire to minimize cost for the storage of large volumes of information for relatively longer terms has lead to increased access times to selected portions of that information, which times have been reduced only through significantly increased expense undertaken in providing parallel operations in either the database machines or the computer systems being used.
Thus, overcoming the problem of reducing the time in which access to a storage site in a plurality of storage sites which are only available sequentially to a storing and sensing means, and often available sequentially only after a delay permitting the storing and sensing means to reach the sequence of storage sites of interest, has proved to be expensive. As a result, there is a strong desire for a database machine which can improve access times to storage sites which are available successively only in sequence, but without making such machines prohibitively expensive.